import myqueue.MyCircularQueue;
import myqueue.MyQueue;
import testdemo.MyStack;

import java.util.Stack;

/**
 * Stack题
 * 队列
 */
public class Test {
    /**
     * 队列实现栈->testdemo -> MyStack演示
     * @param args
     */
    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(1);
        myStack.push(2);
        System.out.println(myStack.top()); // 返回 2
        System.out.println(myStack.pop()); // 返回 2
        System.out.println(myStack.empty());// 返回 false
    }
    public static void main9(String[] args) {
        /**
         * 双端队列(deque）:是指允许两端都可以进行入队和出队操作的队列
         */
    }
    /**
     * 循环队列
     */
    public static void main8(String[] args) {
        MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
        System.out.println(circularQueue.enQueue(1));  // 返回 true
        System.out.println(circularQueue.enQueue(2));  // 返回 true
        System.out.println(circularQueue.enQueue(3));  // 返回 true false
        System.out.println(circularQueue.enQueue(4));  // 返回 false，队列已满
        System.out.println(circularQueue.Rear());  // 返回 3
        System.out.println(circularQueue.isFull());  // 返回 true
        System.out.println(circularQueue.deQueue());  // 返回 true
        System.out.println(circularQueue.enQueue(4));  // 返回 true
        System.out.println(circularQueue.Rear());  // 返回 4 0
    }
    /**
     * 队列的自我实现->MyQueue演示
     */
    public static void main7(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.offer(1);
        myQueue.offer(2);
        myQueue.offer(3);
        myQueue.offer(4);
        myQueue.offer(5);
        System.out.println(myQueue.poll());
        System.out.println(myQueue.peek());
        System.out.println(myQueue.isEmpty());
    }
    public static void main6(String[] args) {
        /**
         * 队列的概念:只允许在一端插入 一端删除数据的线性操作的特殊线性表
         * @param args
         */
    }
    /**
     * 栈 虚拟机栈 栈帧的区别
     * @param args
     */
    public static void main5(String[] args) {
        /**
         * 栈:后进先出的一种结构
         * 虚拟机栈:JVM的一块内存空间
         * 栈帧:调用方法时,为方法开辟的内存空间
         */
    }
    /**
     * 最小栈->MinStack实现
     */
    public static void main4(String[] args) {
        MinStack minStack = new MinStack();
//        ["MinStack","push","push","push","getMin","pop","top","getMin"]
//[[],[-2],[0],[-3],[],[],[],[]]
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.top());
        System.out.println(minStack.getMin());
    }
    /**
     1.入栈
     2.判断是否相等
     3.相等,出栈,不等,继续入栈
     4.stack为空/popV遍历完成,则证明为该push出栈序列,反之,则不是.
     */
    public static boolean isPopOrder (int[] pushV, int[] popV) {
        Stack<Integer> stack = new Stack<>();

        int j = 0;
        for(int i = 0;i < pushV.length;i++) {
            stack.push(pushV[i]);

            while(!stack.isEmpty() && j < popV.length && stack.peek() == popV[j]) {//判断
                j++;
                stack.pop();
            }
        }
        // return stack.isEmpty();
        return j >= pushV.length;
    }

    public static void main3(String[] args) {
        int[] array1 = {1,2,3,4,5};
        int[] array2 = {4,1,3,2,5};
        System.out.println(isPopOrder(array1, array2));
    }
    /**
     1.左括号压栈
     2.右括号出栈比较
     */
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for(int i = 0;i < s.length();i++) {
            char ch = s.charAt(i);
            if(ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            }else {
                if(stack.isEmpty()) {//为空
                    return false;
                }else {//不为空
                    char ch2 = stack.peek();
                    if(ch2 == '(' && ch == ')' || ch2 == '[' && ch == ']'
                            || ch2 == '{' && ch == '}') {
                        stack.pop();
                    }else {
                        return false;
                    }
                }
            }
        }

        if(!stack.isEmpty()) {
            return false;
        }

        return true;
    }

    public static void main2(String[] args) {
        System.out.println(isValid("()"));
        System.out.println(isValid("()[]{}"));
        System.out.println(isValid("(]"));
    }
    /**
     * 逆波兰表达式求值
     * @param tokens
     * @return
     */
    public static int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(int i = 0;i < tokens.length;i++) {
            if(!isOperation(tokens[i])) {
                int val = Integer.valueOf(tokens[i]);
                stack.push(val);
            }else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch(tokens[i]) {
                    case "+":
                        int num3 = num1 + num2;
                        stack.push(num3);
                        break;
                    case "-":
                        num3 = num1 - num2;
                        stack.push(num3);
                        break;
                    case "*":
                        num3 = num1 * num2;
                        stack.push(num3);
                        break;
                    case "/":
                        num3 = num1 / num2;
                        stack.push(num3);
                        break;
                }
            }
        }
        return stack.pop();
    }
    private static boolean isOperation(String str) {
        if(str.equals("+") || str.equals("-")
                || str.equals("*") || str.equals("/")) {
            return true;
        }
        return false;
    }
    public static void main1(String[] args) {
        Stack<Integer> stack = new Stack<>();
        String[] tokens = {"4","13","5","/","+"};
        int ret = evalRPN(tokens);
        System.out.println(ret);
    }
}
